package test;

public class MyList<E> {
    private Node head;

    /**
     * 增加节点
     *
     * @param element     节点数据
     * @param nextElement 节点的后继节点数据
     */
    public void add(E element, E nextElement) {
        if (element == null) {
            return;
        }
        //创建新节点
        Node node = new Node(element);
        //如果链表为空，直接将头指向新节点
        if (head == null) {
            head = node;
        } else {
            Node p = head;
            //循环至链表尾部
            for (; p.next != null; p = p.next) {
            }
            p.next = node;
            node.next = getNode(nextElement);
        }
    }

    /**
     * 根据数据获取节点
     *
     * @param element
     * @return
     */
    private Node getNode(E element) {
        if (element == null)
            return null;
        for (Node p = head; p != null; p = p.next) {
            if (element.equals(p.data)) {
                return p;
            }
        }
        return null;
    }

    /**
     * 判断是否有环，返回快慢指针相交的节点
     *
     * @return
     */
    public Node hasCycle() {
        Node slow = head, fast = head;
        while (slow != null && fast.next != null) {
            slow = slow.next;

            if((fast = fast.next.next) == null){
                return null;
            }

            if (slow == fast) {  //慢指针和快指针指向相同的节点
                return slow;
            }
        }
        return null;
    }

    /**
     * 获取环的入口
     *
     * @return
     */
    public E getInNode() {
        Node node = hasCycle();
        if (node == null) {
            return null;
        }
        Node first = head, second = node;   //双指针分别指向链表头和快慢指针相交的节点
        while (first != second) {
            first = first.next;
            second = second.next;
        }
        return first.data;
    }

    private class Node {
        E data;
        Node next;

        Node(E data) {
            this.data = data;
        }

        Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

    }

    public static void main(String[] args) {
        MyList<Integer> list = new MyList<>();
        list.add(1, null);
        list.add(2, null);
        list.add(3, null);
        list.add(4, null);
        list.add(5, null);
        list.add(6, null);
        list.add(7, 8);
        list.add(8, 9);
        list.add(9, 6);

        if (list.hasCycle() == null) {
            System.out.println("不存在环");
        } else {
            System.out.println("存在环");
        }
        System.out.println("环的入口为：" + list.getInNode());
    }
}
